#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;        //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType;     //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode{
    ElemType   data;       //数据域
    struct LNode  *next;   //指针域
}LNode, *LinkList;         // *LinkList为Lnode类型的指针，用于定义链表头指针

// 初始化线性表
Status InitList(LinkList &L) {
    L = new LNode;        // 创建头结点
    if (!L) return OVERFLOW;
    L->next = NULL;       // 头结点指针域置空
    return OK;
}

// 销毁线性表
Status DestroyList(LinkList &L) {
    LinkList p;
    while (L) {
        p = L;
        L = L->next;
        delete p;
    }
    return OK;
}

// 求线性表长度
int ListLength(LinkList L) {
    int length = 0;
    LinkList p = L->next;  // p指向第一个结点
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

// 判断线性表是否为空
Status ListEmpty(LinkList L) {
    return (L->next == NULL) ? OK : ERROR;
}

// 按位序求值
Status GetElem(LinkList L, int i, ElemType &e) {
    //if (i < 1) return ERROR;
    
    LinkList p = L->next;  // p指向第一个结点
    int j = 1;
    
    while (p && j < i) {   // 寻找第i个结点
        p = p->next;
        j++;
    }
    
    if (!p || j > i) return ERROR;  // 第i个元素不存在
    e = p->data;
    return OK;
}

// 按值查找位序
int LocateElem(LinkList L, ElemType e) {
    LinkList p = L->next;  // p指向第一个结点
    int i = 1;
    
    while (p) {
        if (p->data == e) return i;
        p = p->next;
        i++;
    }
    return 0;  // 未找到返回0
}

// 插入元素
Status ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) return ERROR;
    
    LinkList p = L;
    int j = 0;
    
    // 寻找第i-1个结点
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i - 1) return ERROR;  // i大于表长+1或者i<1
    
    LinkList s = new LNode;
    if (!s) return OVERFLOW;
    
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

// 删除元素
Status ListDelete(LinkList &L, int i, ElemType &e) {
    if (i < 1) return ERROR;
    
    LinkList p = L;
    int j = 0;
    
    // 寻找第i-1个结点
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (!(p->next) || j > i - 1) return ERROR;  // 删除位置不合理
    
    LinkList q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return OK;
}

// 从文件导入数据
Status ImportList(LinkList &L, const char *filename) {
    ifstream file(filename);
    if (!file) {
        cout << "无法打开文件 " << filename << endl;
        return ERROR;
    }
    
    // 清空原有链表
    LinkList p = L->next;
    while (p) {
        LinkList temp = p;
        p = p->next;
        delete temp;
    }
    L->next = NULL;
    
    ElemType data;
    LinkList tail = L;  // 尾指针
    
    cout << "从文件导入的数据：";
    while (file >> data) {
        LinkList s = new LNode;
        if (!s) return OVERFLOW;
        
        s->data = data;
        s->next = NULL;
        tail->next = s;
        tail = s;
        cout << data << " ";
    }
    cout << endl;
    
    file.close();
    return OK;
}

// 导出数据到文件
Status ExportList(LinkList L, const char *filename) {
    ofstream file(filename);
    if (!file) {
        cout << "无法创建文件 " << filename << endl;
        return ERROR;
    }
    
    LinkList p = L->next;
    cout << "导出到文件的数据：";
    while (p) {
        file << p->data << " ";
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
    
    file.close();
    return OK;
}

// 显示线性表
void DisplayList(LinkList L) {
    if (ListEmpty(L) == OK) {
        cout << "线性表为空" << endl;
        return;
    }
    
    LinkList p = L->next;
    cout << "线性表内容：";
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 菜单显示
void ShowMenu() {
    cout << "\n========== 线性表链式存储操作菜单 ==========" << endl;
    cout << "1. 初始化线性表" << endl;
    cout << "2. 销毁线性表" << endl;
    cout << "3. 求线性表长度" << endl;
    cout << "4. 判断线性表是否为空" << endl;
    cout << "5. 按位序求值" << endl;
    cout << "6. 按值查找位序" << endl;
    cout << "7. 插入元素" << endl;
    cout << "8. 删除元素" << endl;
    cout << "9. 从文件导入数据" << endl;
    cout << "10. 导出数据到文件" << endl;
    cout << "11. 显示线性表" << endl;
    cout << "0. 退出程序" << endl;
    cout << "===========================================" << endl;
    cout << "请选择操作：";
}

int main() {
    LinkList L = NULL;
    int choice;
    ElemType e;
    int position;
    
    do {
        ShowMenu();
        cin >> choice;
        
        switch (choice) {
            case 1:  // 初始化
                if (InitList(L) == OK)
                    cout << "线性表初始化成功！" << endl;
                else
                    cout << "线性表初始化失败！" << endl;
                break;
                
            case 2:  // 销毁
                if (L) {
                    DestroyList(L);
                    L = NULL;
                    cout << "线性表销毁成功！" << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 3:  // 求长度
                if (L) {
                    cout << "线性表长度为：" << ListLength(L) << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 4:  // 判空
                if (L) {
                    if (ListEmpty(L) == OK)
                        cout << "线性表为空" << endl;
                    else
                        cout << "线性表不为空" << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 5:  // 按位序求值
                if (L) {
                    cout << "请输入要查找的位置：";
                    cin >> position;
                    if (GetElem(L, position, e) == OK)
                        cout << "第" << position << "个元素的值是：" << e << endl;
                    else
                        cout << "查找失败，位置不合法！" << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 6:  // 按值查找
                if (L) {
                    cout << "请输入要查找的值：";
                    cin >> e;
                    position = LocateElem(L, e);
                    if (position > 0)
                        cout << "元素" << e << "的位置是：" << position << endl;
                    else
                        cout << "未找到该元素！" << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 7:  // 插入
                if (L) {
                    cout << "请输入要插入的位置和值（位置 值）：";
                    cin >> position >> e;
                    if (ListInsert(L, position, e) == OK)
                        cout << "插入成功！" << endl;
                    else
                        cout << "插入失败，位置不合法！" << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 8:  // 删除
                if (L) {
                    cout << "请输入要删除的位置：";
                    cin >> position;
                    if (ListDelete(L, position, e) == OK)
                        cout << "删除成功！删除的元素是：" << e << endl;
                    else
                        cout << "删除失败，位置不合法！" << endl;
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 9:  // 从文件导入
                if (L) {
                    char filename[100];
                    cout << "请输入文件名：";
                    cin >> filename;
                    ImportList(L, filename);
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 10:  // 导出到文件
                if (L) {
                    char filename[100];
                    cout << "请输入文件名：";
                    cin >> filename;
                    ExportList(L, filename);
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 11:  // 显示
                if (L) {
                    DisplayList(L);
                } else {
                    cout << "线性表未初始化！" << endl;
                }
                break;
                
            case 0:  // 退出
                if (L) {
                    DestroyList(L);
                }
                cout << "程序退出，感谢使用！" << endl;
                break;
                
            default:
                cout << "无效的选择，请重新输入！" << endl;
                break;
        }
    } while (choice != 0);
    
    return 0;
}
